package com.yun.algorithmproblem.leetcode;

/**
 * 3115. 质数的最大距离
 * 给你一个整数数组 nums。
 *
 * 返回两个（不一定不同的）质数在 nums 中 下标 的 最大距离。
 * 示例 1：
 * 输入： nums = [4,2,9,5,3]
 * 输出： 3
 * 解释： nums[1]、nums[3] 和 nums[4] 是质数。因此答案是 |4 - 1| = 3。
 *
 * 示例 2：
 * 输入： nums = [4,8,2,8]
 * 输出： 0
 * 解释： nums[2] 是质数。因为只有一个质数，所以答案是 |2 - 2| = 0。
 *
 * 提示：
 * 1 <= nums.length <= 3 * 105
 * 1 <= nums[i] <= 100
 * 输入保证 nums 中至少有一个质数。
 */
public class Leetcode3115 {
    public static void main(String[] args) {

    }

    private static final int MX=101;
    private static final boolean[] NOT_PRIme=new boolean[MX];

    static {
        NOT_PRIme[1]=true;
        for (int i=2;i*i<MX;i++){
            if(NOT_PRIme[i]){
                continue;
            }
            for (int j=i*i;j<MX;j+=i){
                NOT_PRIme[j]=true;
            }
        }
    }

    public int maximumPrimeDifference(int[] nums) {
        int i=0;
        while (NOT_PRIme[nums[i]]){
            i++;
        }
        int j= nums.length-1;
        while (NOT_PRIme[nums[j]]){
            j--;
        }
        return j-i;
    }
}
